//a^n%b;
ll expmod(ll a,ll n,ll b)
{
	ll t;
	if(n==0LL)	return 1LL%b;
	if(n==1LL)	return a%b;
	t=expmod(a,n/2,b);
	t=t*t%b;
	if((n&1)==1)	t=t*a%b;
	return t;
}
